#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "grafo.h"
#define FALSE 0
#define TRUE 1

/**
 * Faz a alocação dinâmica de uma matriz
 *
 * m -> número de linhas da matriz
 * n -> número de colunas da matriz
 */
int **alocaMatriz(int m, int n) {
	int **v;
	int   i;
	if (m < 1 || n < 1) {
		printf ("** Erro: Parametro invalido **\n");
		return (NULL);
	}

	v = (int **) calloc (m, sizeof(int *));
	if (v == NULL) {
		printf ("** Erro: Memoria Insuficiente **");
		return (NULL);
	}

	for ( i = 0; i < m; i++ ) {
		v[i] = (int*) calloc (n, sizeof(int));
		if (v[i] == NULL) {
			printf ("** Erro: Memoria Insuficiente **");
			return (NULL);
		}
	}
	return (v);
}

/**
 * Libera a memória alocada por uma matriz
 */
int **liberaMatriz(int **matriz, int n) {

	int i;
	for(i = 0; i < n-1; i ++) {
		free(matriz[i]);
	}
	free(matriz);
	return (NULL);

}

/**
 * Inicializa um grafo de n vértices sem arestas
 */
void criaGrafoVazio(TipoGrafo *grafo, int n) {

	int **matriz = alocaMatriz(n,n);

	int i,j;
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++) {
			matriz[i][j] = 0;
		}
	}

	grafo->matriz = matriz;
	grafo->NumVertices = n;
	grafo->NumArestas = 0;

}

/**
 * Insere uma aresta entre os vértices v1 e v2 com um determinado peso
 */
void insereAresta(TipoGrafo *grafo, int v1, int v2, int peso) {
	grafo->matriz[v1][v2] = peso;
	grafo->NumArestas += grafo->NumArestas + 1;
}

/**
 * Verifica se existe uma aresta ligando os vertices v1 e v2
 */
int existeAresta(TipoGrafo *grafo, int v1,int v2) {
	return grafo->matriz[v1][v2] > 0;
}

int listaAdjVazia(TipoGrafo *grafo, int v, int n) {
	int aux = 0;
	int listaVazia = TRUE;
	while(aux < n && listaVazia) {
		if(grafo->matriz[v][aux] > 0) {
			listaVazia = FALSE;
		} else {
			aux++;
		}
	}

	return listaVazia == TRUE;
}

int primeiroListaAdj(TipoGrafo *grafo, int v, int n) {
	int resultado = -1;
	int aux = 0;
	int listaVazia = TRUE;
	while(aux<n && listaVazia) {
		if(grafo->matriz[v][aux]  > 0 ) {
			resultado = aux;
			listaVazia = FALSE;
		} else {
			aux++;
		}
	}

	if(aux == n) {
		printf("[Erro] Lista de Adjacencia Vazia");
	}
	return resultado;
}

void proxAdj(TipoGrafo *grafo, int n, int v, int *adj, int *peso, int *prox, int *fimListaAdj) {

	*adj = *prox;
	*peso = grafo->matriz[v][*prox];
	(*prox)++;

	while(*prox < n && grafo->matriz[v][*prox] == 0) {
		(*prox)++;
	}

	if(*prox == n) *fimListaAdj= TRUE;
}

void retiraAresta(TipoGrafo *grafo, int v1, int v2, int *peso) {
	if(grafo->matriz[v1][v2] == 0) {
		printf("Aresta não existe");
		*peso = -1;
	} else {
		*peso = grafo->matriz[v1][v2];
		grafo->matriz[v1][v2] = 0;
		grafo->NumArestas = grafo->NumArestas - 1;
	}
}

void imprimeGrafo(TipoGrafo *grafo, int n) {
	int i,j;

	for(i = 0; i < n - 1; i++) {
		printf("%3d", i);
	}
	printf("\n");
	for(i = 0; i < n - 1; i++) {
		printf("\n%3d", i);
		for(j = 0; j < n - 1; j++) {
			printf("%3d", grafo->matriz[i][j]);
		}
		printf("\n");
	}
}

int **liberaGrafo(TipoGrafo *grafo, int n) {
	liberaMatriz(grafo->matriz,n);
	free(grafo);
	return (NULL);
}
